package arithmetic.twosum;

import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;

/**
 * @author zhangzg
 * @date 2022/10/9
 *
 */
public class Test {

    public static void main(String[] args) {
        int[] ints = {3,2,4,6};
        int target=11;
        int[] calc = calc(ints, target);
        System.out.println(Arrays.toString(calc));

        int[] calc1 = calc1(ints, target);
        System.out.println(Arrays.toString(calc1));

        System.out.println(isTrue(ints,target));
    }

    public static boolean isTrue(int[] nums, int target){
        if(nums == null || nums.length < 2){
            return false;
        }
        if (nums.length == 2){
            return nums[0] + nums[1] == target;
        }
        Arrays.sort(nums);
        int left = 0;
        int right = nums.length - 1;
        while (left < right){
            if(nums[left] + nums[right] == target){
                return true;
            }else if (nums[left] + nums[right] > target){
                right--;
            }else {
                left++;
            }
        }
        return false;
    }

    /**
     * 时间复杂度O(n^2)
     * @param nums
     * @param target
     * @return
     */
    public static int[] calc(int[] nums,int target){
        int[] result = new int[2];
        for (int i=0;i<nums.length;i++){
            int i1 = nums[i];
            for (int j=i+1;j<nums.length;j++){
                int i2 = nums[j];
                if(i1+i2==target){
                    result[0]=i;
                    result[1]=j;
                    return result;
                }
            }
        }
        return result;
    }

    /**
     * 利用hashmap提高时间复杂度
     * key为元素值，value为数组下标
     * 时间复杂度O(n)
     * @param nums
     * @param target
     * @return
     */
    public static int[] calc1(int[] nums,int target){
        //key为元素值，value为数组下标
        Map map = new HashMap<Integer, Integer>();
        int[] result = new int[2];
        for (int i=0;i<nums.length;i++){
            int num = nums[i];
            if (map.get(target-num)!=null) {
                result[0]=(Integer) map.get(target-num);;
                result[1]=i;
                return result;
            }else {
                map.put(num,i);
            }
        }
        return result;
    }

}
